
#include <iostream>
#include <cstdlib>
#include "../include/Computer.h"
#include "../include/Board.h"
#include <vector>

using namespace std;

// 搜索函数
vector<int> Computer::nextMoveAlphaBeta(Board &board)
{
	vector<int> v = {0, 0};
	int M = INT_MIN, x = -1, y = -1;

	for (int i = 0; i <= N - 1; i++)
	{
		for (int j = 0; j <= N - 1; j++)
		{
			if (board.getValue(i, j) == '.' && adjacentPlaced(board, i, j)) // 判断(x,y)是否可以下棋 && 四周是否有棋
			{
				int temp = minimaxAlphaBeta(board, 2, true, INT_MIN, INT_MAX, i, j);
				if (M < temp)
				{
					M = temp;
					x = i;
					y = j;
				}
			}
		}
	}
	// 如果搜索不到,使用随机数替代
	if ((x == -1 && y == -1) || board.checkEmpty(x, y) == false)
	{
		while (1)
		{
			x = rand() % N;
			y = rand() % N;
			if (board.getValue(x, y) == '.' && board.checkEmpty(x, y) == true)
				break;
		}
	}
	v[0] = x;
	v[1] = y;
	return v;
}

// minimax算法与alpha-beta实现AI下棋
// 分数越高对AI有利，分数越低对玩家有利
// 如果在(x,y)的移动是AI走的，isMax = true
int Computer::minimaxAlphaBeta(Board &board, int depth, bool isMax, int alpha, int beta, int x, int y)
{
	// 获取AI或玩家下棋的符号
	char c = isMax ? board.getComputerSymbol() : board.getPlayerSymbol();
	// 下棋
	board.setValue(x, y, c);

	if (board.win(x, y))
	{ // 如果能判断某方胜利
		board.setValue(x, y, '.');
		if (isMax)
		{ // AI有利，直接给max分
			return INT_MAX;
		}
		else
		{ // 对AI不利,直接给min分
			return INT_MIN;
		}
	}
	else if (board.draw()) //平局判断
	{
		board.setValue(x, y, '.');
		return 0;
	}
	if (depth == 0)
	{
		int value = 0;
		if (checkVisitedBoard(board) == true) // 检查是否曾经计算过当前所需的评估值
		{
			value = getEvaluation(board); // 获得曾经计算过的评估值
		}
		else
		{
			value = evaluation(board, isMax); // 进行计算评估
			insertToHashMap(board, value);	  // 保存当前评估值,以供重复调用
		}
		board.setValue(x, y, '.');

		return value;
	}

	// 将可用的X位置存到firstCoord，将可用的Y位置存到secondCoord
	vector<int> firstCoord;
	vector<int> secondCoord;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{ // 判断(x,y)是否可以下棋 && 四周是否有棋
			if (board.getValue(i, j) == '.' && adjacentPlaced(board, i, j))
			{
				firstCoord.push_back(i);
				secondCoord.push_back(j);
			}
		}
	}

	int len = (int)firstCoord.size();
	if (isMax == true)
	{ // 玩家下棋，分数尽可能小
		int m = INT_MAX;
		for (int i = 0; i < len; i++)
		{
			int temp = minimaxAlphaBeta(board, depth - 1, false, alpha, beta, firstCoord[i], secondCoord[i]);
			if (m > temp)
			{
				m = temp;
			}
			if (beta > m)
			{
				beta = m;
			}
			if (alpha >= beta)
			{
				break;
			}
		}
		//恢复棋盘
		board.setValue(x, y, '.');

		return m;
	}
	else
	{ // 电脑下棋，分数尽可能大
		int M = INT_MIN;
		for (int i = 0; i < len; i++)
		{
			int temp = minimaxAlphaBeta(board, depth - 1, true, alpha, beta, firstCoord[i], secondCoord[i]);
			if (M < temp)
			{
				M = temp;
			}
			if (alpha < M)
			{
				alpha = M;
			}
			if (alpha >= beta)
			{
				break;
			}
		}
		//恢复棋盘
		board.setValue(x, y, '.');

		return M;
	}
}

int Computer::evaluation(Board &board, bool isMax)
{ // 如果isMax为真，将在(x,y)处移动。
	int sum = 0;
	vector<int> computerPattern(M + 1, 0);  // 记录AI的各种棋型数量 M为5
	vector<int> playerPattern(M + 1, 0);  // // 记录玩家的各种棋型数量
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (board.getValue(i, j) != '.')	//如果此位置不为空
			{

				char c = board.getValue(i, j);
				bool needMax = c == board.getComputerSymbol();	//辨别该位置是否AI下的棋  是否需要最大化评估值。
				int sameSymbol = 1; // 列检查
				//统计当前列所有棋的数量
				//   “/”这个方向检查
				int k = 1;
				while (i - k >= 0 && board.getValue(i - k, j) == c)  // 向上统计相同棋子数量
				{
					sameSymbol++;
					k++;
				}
				int l = 1;
				while (i + l <= N - 1 && board.getValue(i + l, j) == c) // 向下统计相同棋子数
				{
					sameSymbol++;
					l++;
				}
				//已经胜利,直接标记max or min
				if (sameSymbol >= M)
				{
					if (needMax)
						computerPattern[M]++;  // AI的M子连珠数量加1
					else
						playerPattern[M]++;  //// 玩家的M子连珠数量加1
				}
				//有4个棋连在一起
				else if (sameSymbol == M - 1 && (board.checkEmpty(i - k, j) || board.checkEmpty(i + l, j)))   // 如果相同棋子数量为 4 且至少一端有空位时
				{
					if (needMax)
						computerPattern[M - 1]++;
					else
						playerPattern[M - 1]++;
				}
				//有3个棋连在一起
				else if (sameSymbol == M - 2 && (board.checkEmpty(i - k, j) || board.checkEmpty(i + l, j)))   // 如果相同棋子数量为 3 且至少一端有空位时
				{  
					if (needMax)
						computerPattern[M - 2]++;   // AI的 3 子连珠数量加1
					else
						playerPattern[M - 2]++;   //玩家的 3 子连珠数量加1
				}
				//有2个棋连在一起
				else if (sameSymbol == M - 2 && (board.checkEmpty(i - k, j) && board.checkEmpty(i + l, j)))   // 如果相同棋子数量为 2 且两端都有空位
				{
					if (needMax)
						computerPattern[M - 3]++;  // AI的 2 子连珠数量加1
					else
						playerPattern[M - 3]++;  //玩家的 2 子连珠数量加1
				}
				//只有1个棋
				else if (sameSymbol == M - 3 && board.checkEmpty(i - k, j) && board.checkEmpty(i + l, j))  // 如果相同棋子数量为 1 且两端都有空位
				{
					if (needMax)
						computerPattern[M - 4]++;  // AI的 1 子连珠数量加1
					else
						playerPattern[M - 4]++;  //玩家的 1 子连珠数量加1
				}

				//-------------------------------------------------------------------------------
				sameSymbol = 1; // “\”这个方向检查 ， 连续相同棋子的数量重置为1
				k = 1;
				while (j - k >= 0 && board.getValue(i, j - k) == c)   
				{
					sameSymbol++;
					k++;
				}
				l = 1;
				while (j + l <= N - 1 && board.getValue(i, j + l) == c)
				{
					sameSymbol++;
					l++;
				}
				
				if (sameSymbol >= M)
				{
					if (needMax)
						computerPattern[M]++;
					else
						playerPattern[M]++;
				}
				else if (sameSymbol == M - 1 && (board.checkEmpty(i, j - k) || board.checkEmpty(i, j + l)))
				{
					if (needMax)
						computerPattern[M - 1]++;
					else
						playerPattern[M - 1]++;
				}
				else if (sameSymbol == M - 2 && (board.checkEmpty(i, j - k) || board.checkEmpty(i, j + l)))
				{
					if (needMax)
						computerPattern[M - 2]++;
					else
						playerPattern[M - 2]++;
				}
				else if (sameSymbol == M - 2 && (board.checkEmpty(i, j - k) && board.checkEmpty(i, j + l)))
				{
					if (needMax)
						computerPattern[M - 3]++;
					else
						playerPattern[M - 3]++;
				}
				else if (sameSymbol == M - 3 && board.checkEmpty(i, j - k) && board.checkEmpty(i, j + l))
				{
					if (needMax)
						computerPattern[M - 4]++;
					else
						playerPattern[M - 4]++;
				}

				//--------------------------------------------------------------

				sameSymbol = 1; // “|”这个方向检查
				k = 1;
				while (i - k >= 0 && j - k >= 0 && board.getValue(i - k, j - k) == c)
				{
					sameSymbol++;
					k++;
				}
				l = 1;
				while (i + l <= N - 1 && j + l <= N - 1 && board.getValue(i + l, j + l) == c)
				{
					sameSymbol++;
					l++;
				}

				if (sameSymbol >= M)
				{
					if (needMax)
						computerPattern[M]++;
					else
						playerPattern[M]++;
				}
				else if (sameSymbol == M - 1 && (board.checkEmpty(i - k, j - k) || board.checkEmpty(i + l, j + l)))
				{
					if (needMax)
						computerPattern[M - 1]++;
					else
						playerPattern[M - 1]++;
				}
				else if (sameSymbol == M - 2 && (board.checkEmpty(i - k, j - k) || board.checkEmpty(i + l, j + l)))
				{
					if (needMax)
						computerPattern[M - 2]++;
					else
						playerPattern[M - 2]++;
				}
				else if (sameSymbol == M - 2 && (board.checkEmpty(i - k, j - k) && board.checkEmpty(i + l, j + l)))
				{
					if (needMax)
						computerPattern[M - 3]++;
					else
						playerPattern[M - 3]++;
				}
				else if (sameSymbol == M - 3 && board.checkEmpty(i - k, j - k) && board.checkEmpty(i + l, j + l))
				{
					if (needMax)
						computerPattern[M - 4]++;
					else
						playerPattern[M - 4]++;
				}
			}
		}
	}
	if (computerPattern[M] > 0)  //ai胜利
		return INT_MAX;
	if (playerPattern[M] > 0)   //玩家胜利
		return INT_MIN;
	//将全部分数进行累加
	int x = 1;
	sum += computerPattern[1];  // 累加ai在1子连珠的得分
	sum -= playerPattern[1] * 5;  // 减去玩家在1子连珠的得分（权重为5）
	for (int i = 2; i < M; i++)
	{
		x *= 100;  //每多一个棋连在一起,局部得分*100
		sum += computerPattern[i] * x;  // 累加ai在i子连珠的得分
		sum -= playerPattern[i] * x * 10; // 减去玩家在i子连珠的得分（权重为局部得分的10倍）
	}
	return sum;
}
// 判断(x,y)四周是否有棋
bool Computer::adjacentPlaced(Board &board, int x, int y)
{

	bool value = false;
	if (board.getValue(x, y) != '.')
		return false;
	vector<vector<int>> adjacent = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}};
	for (auto d : adjacent)
	{
		// 此位置是否合法
		if (x + d[0] >= 0 && y + d[1] >= 0 && x + d[0] <= N - 1 && y + d[1] <= N - 1)
		{
			value = value || (board.getValue(x + d[0], y + d[1]) != '.');
		}
	}
	return value;
}

// 检查当前棋盘是否在hashMap里面存储,若已存在返回true
bool Computer::checkVisitedBoard(Board &board)
{
	string s = board.toString();
	if (hashMap.find(s) != hashMap.end())
	{
		return true;
	}
	return false;
}

// 如果当前棋盘已存在hashMap中,便只需要将其取出,减少评估函数计算量
int Computer::getEvaluation(Board &board)
{
	if (checkVisitedBoard(board))
	{
		return hashMap[board.toString()];
	}
	return -1;
}

// 将当前棋盘存储到hashMap,并设置对应值为eval
void Computer::insertToHashMap(Board &board, int eval)
{
	string s = board.toString();
	hashMap[s] = eval;
	return;
}
